In a wireless personal area network known as a piconet, with the piconet network controller (PNC) scheduling overall communications within the network, the PNC and each associated device (DEV) may use multi-antenna directional communications between itself and the PNC to reduce the potential interference between the various devices in the network. The antenna parameters for such directional communication may be established during a beam-forming antenna training session between the two devices, with the time for this training session allocated by the PNC. But once established, if this directional link is lost the two devices must perform beam training again to reestablish the directional link. Under conventional procedures, the DEV will determine the link is lost when it doesn't receive a beacon, the DEV will use the Contention Access Period (CAP) to request re-establishment of the link, and the PNC will subsequently allocate a time slot for this new beam training in a subsequent superframe. But if multiple devices lose their links at the same time (e.g., if the PNC is physically moved or rotated), there may be too many devices contending for access to the PNC during the CAP, resulting in collisions and failure to achieve the desired communication. Since not all the DEV's are likely to get through to the PNC in the same superframe, the re-establishment of the links may likely be spread across several superframes, with a separate omnidirectional transmission to each device, possibly preventing communications for other devices throughout the network during those periods.